#ifndef DATA_STRUCT___H
#define DATA_STRUCT___H

/* 用户自定义比较函数 */
typedef int (*compar_t)(const void *, const void *);	
/* 用户自定义修改关键字函数,
 * 前者参数为用户自定义数据结构,
 * 后者参数为要修改的key值 
 */
typedef void (*change_key_t)(void *, const void *); 

/* 队列元素结构 */
typedef struct pq_element
{
	void *data;
	int	index;	//用于记录该节点所位于数组中的下标值
}PQ_element;

typedef struct PQ_desc
{
	compar_t	compar; 
	change_key_t change_key;
	int heap_size;	/* 堆的大小 */
	int len;	/* 当前优先级队列数组中可容纳的最大长度 */
	PQ_element **base;
}PQ;

/* 创建优先级队列,nmemb为队列中包含元素的个数,compar为比较函数,change_key为修改关键字函数 */
PQ *create_PQ(int nmemb, compar_t compar, change_key_t change_key);
void destroy_PQ(PQ *desc); //销毁优先级队列
int insert_PQ(PQ *desc, PQ_element *x);	//向队列中插入一个元素,元素为前面定义的元素结构
int delete_PQ(PQ *desc, const PQ_element *x);	//删除队列中的一个元素,该元素由x引用
PQ_element *root_PQ(PQ *desc);	//得到优先级队列的对头元素
PQ_element *extract_PQ(PQ *desc);	//得到优先级队列的对头元素并将对头元素从优先级队列中删除
/* 
 * 将key指向的用户结构赋值给x指向的用户结构,并改变x在队列中的位置 
 * 这里将调用用户自定义的change_key函数,
 * 并将key和x做为change_key函数的参数传递
 */
void change_key_PQ(PQ *desc, PQ_element *x, const void *key); //将优先级队列desc中的元素x中的关键字修改为key
PQ_element *malloc_PQ(size_t size); //申请节点空间
void free_PQ(PQ_element *ptr); //释放由malloc_PQ申请的节点空间.

#define ELEMENT_DATA(pq_element) ((pq_element)->data)	//返回节点元素中用户自定义数据结构的指针
#define CLEAN_ELEMENT(pq_element) ((pq_element)->data = NULL)	//将节点元素中的用户数据指针清除
#define INDEX_ELEMENT(pq_element) ((pq_element)->index)	//返回节点元素在堆中的索引值
#define PQ_SIZE(desc) ((desc)->heap_size) //优先级队列中队列的长度
#define PQ_LEN(desc) ((desc)->len) //目前能容纳的元素的最大个数

#endif
